package scu.maqiang.numeric;

import java.util.Arrays;

public class Algorithms {
	/**
	 * 选择排序法
	 * @param x 要排序的数据, 最后输出为排序好的数据
	 * @param p 排列组装, 表示排序好的x数组中位于第i位的元素在原来数组中的p[i]个位置
	 * @param isascending true 升序排列, false 降序排列
	 */
	public static void selectionSort(int[] x, int[] p, boolean isascending) {
		int n = x.length;
		Arrays.setAll(p, i -> i);
		if (isascending) {
			for(int i = 0; i < n - 1; i++) {
				int min = x[i];
				int minIdx = i;
				for(int j = i + 1; j < n; j++) {
					if (x[j] < min) {
						min = x[j];
						minIdx = j;
					}
				}
				if (minIdx != i) {
					int temp = x[i];
					x[i] = x[minIdx];
					x[minIdx] = temp;
					temp = p[i];
					p[i] = p[minIdx];
					p[minIdx] = temp;
				}
			}
		} else {
			for(int i = 0; i < n - 1; i++) {
				int max = x[i];
				int maxIdx = i;
				for(int j = i + 1; j < n; j++) {
					if (x[j] > max) {
						max = x[j];
						maxIdx = j;
					}
				}
				if (maxIdx != i) {
					int temp = x[i];
					x[i] = x[maxIdx];
					x[maxIdx] = temp;
					temp = p[i];
					p[i] = p[maxIdx];
					p[maxIdx] = temp;
				}
				//System.out.println(Arrays.toString(x));
				//System.out.println(Arrays.toString(p));
				//System.out.println();
			}			
		}
	}

	/**
	 * 选择排序法
	 * @param x 要排序的数据, 最后输出为排序好的数据
	 * @param p 排列组装, 表示排序好的x数组中位于第i位的元素在原来数组中的p[i]个位置
	 * @param isascending true 升序排列, false 降序排列
	 */
	public static void selectionSort(double[] x, int[] p, boolean isascending) {
		int n = x.length;
		Arrays.setAll(p, i -> i);
		if (isascending) {
			for(int i = 0; i < n - 1; i++) {
				double min = x[i];
				int minIdx = i;
				for(int j = i + 1; j < n; j++) {
					if (x[j] < min) {
						min = x[j];
						minIdx = j;
					}
				}
				if (minIdx != i) {
					double temp = x[i];
					x[i] = x[minIdx];
					x[minIdx] = temp;
					int tempIdx = p[i];
					p[i] = p[minIdx];
					p[minIdx] = tempIdx;
				}
			}
		} else {
			for(int i = 0; i < n - 1; i++) {
				double max = x[i];
				int maxIdx = i;
				for(int j = i + 1; j < n; j++) {
					if (x[j] > max) {
						max = x[j];
						maxIdx = j;
					}
				}
				if (maxIdx != i) {
					double temp = x[i];
					x[i] = x[maxIdx];
					x[maxIdx] = temp;
					int tempIdx = p[i];
					p[i] = p[maxIdx];
					p[maxIdx] = tempIdx;
				}
				//System.out.println(Arrays.toString(x));
				//System.out.println(Arrays.toString(p));
				//System.out.println();
			}
		}
	}

		public static void main(String[] args) {
		int[] x = {3, 5, 2, 7, 1};
		int[] xx = x.clone();
		System.out.println("Original array");
		System.out.println(Arrays.toString(x));
		int[] p =  new int[5];
		selectionSort(x, p, true);
		System.out.println("After sorting");
		System.out.println(Arrays.toString(x));
		System.out.println("permunation array");
		System.out.println(Arrays.toString(p));
		
		for (int i = 0; i < 5; i++) {
			System.out.println(xx[p[i]]);
		}

	}
}
